package com.oocl.myProject;

public class LinkList {
	private MyNode head = new MyNode(null, -1, null);
	
	public MyNode getHead() {
		return head;
	}
	public void setHead(MyNode head) {
		this.head = head;
	}

	public LinkList(int[] nums) {
		MyNode p = head;
		MyNode s = new MyNode(head, nums[0], null);
		head.next = s;
		p = p.next;
		for (int i = 1; i < nums.length; i++) {
			MyNode r = new MyNode(p, nums[i], null);
			p.next = r;
			p = p.next;
		}
	}

	public int getListLength(LinkList L) {
		MyNode s = L.head.next;
		int cnt = 0;
		while (s != null) {
			cnt++;
			s = s.next;
		}
		return cnt;
	
	}

	public void printList(LinkList L) {
		MyNode s = L.head.next;
		while (s != null) {
			System.out.print(s.data + "\t");
			s = s.next;
		}
		System.out.print("\n");
	}

	public MyNode getbyIndex(LinkList L, int index) {
		MyNode p = L.head.next;
		int cnt = 1;
		while (cnt < index) {
			p = p.next;
			cnt++;
		}
		return p;
	}

	public void delete(LinkList L, int index){
		MyNode s = L.head;
		MyNode p = s.next;
		MyNode r = p.next;
		int cnt = 0;
		if (index == 1) {
			s.next = r;
			r.pre = s;
			p = null;
		} else if (index == this.getListLength(L)) {
			while (s.next.next != null) {
				s = s.next;
			}
			p.pre = null;
			s.next = null;
			p = null;
		} else if (index > this.getListLength(L) || index < 1) {
			new Exception("Invalid index!");
		} else {
			while (cnt < index - 1) {
				s = s.next;
				p = p.next;
				r = r.next;
				cnt++;
			}
			s.next = r;
			r.pre = s;
		}
	}

	public void insert(LinkList L, int index, int num) {
		MyNode s = L.head;
		MyNode p = s.next;
		int cnt = 0;
		if (index == 1) {
			MyNode r = new MyNode(s, num, p);
			s.next = r;
			p.pre = r;
		} else if (index == this.getListLength(L) + 1) {
			while (s.next != null) {
				s = s.next;
			}
			MyNode r = new MyNode(s, num, null);
			s.next = r;
		} else if (index > this.getListLength(L) + 1 || index < 1) {
			new Exception("Invalid index!");
		} else {
			while (cnt < index) {
				s = s.next;
				p = p.next;
				cnt++;
			}
			MyNode r = new MyNode(s, num, p);
			s.next = r;
			p.pre = r;
		}
	}

	public void sort(LinkList L) {
		for (int i = 0; i < this.getListLength(L) - 1; i++) {
			for (int j = 0; j < this.getListLength(L) - i; j++) {
				if (this.getbyIndex(L, j).data > this.getbyIndex(L, j + 1).data) {
					int temp = this.getbyIndex(L, j).data;
					this.getbyIndex(L, j).data = this.getbyIndex(L, j + 1).data;
					this.getbyIndex(L, j + 1).data = temp;
				}
			}
		}
	}

	public int binarySearch(LinkList L, int qnum) {
		int mid = this.getListLength(L) / 2;
		int high = this.getListLength(L);
		int low = 1;
		int cnt = 0;
		boolean flag = false;
		while (high >= low) {
			if (qnum == this.getbyIndex(L, mid).data) {
				flag = true;
				
//				System.out.println("The number's index is " + mid + "\n" + cnt
//						+ " times query");
				break;
			} else if (qnum < this.getbyIndex(L, mid).data) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
			mid = (high + low) / 2;
			cnt++;
		}
		if (!flag) {
			return 0;
		}
		return cnt;
	}

//	public static void main(String[] args) throws Exception {
//		int[] nums = { 6, 3, 1, 9, 8, 10, 1, 2, 4, 0 };
//		LinkList dlist = new LinkList(nums);
//		System.out.println("Print the initial list:");
//		dlist.printList(dlist);
//
//		System.out.println("Delete at the first position:");
//		dlist.delete(dlist, 1);
//		dlist.printList(dlist);
//
//		System.out.println("Delete at position 4:");
//		dlist.delete(dlist, 4);
//		dlist.printList(dlist);
//
//		System.out.println("Delete at the last position:");
//		dlist.delete(dlist, 8);
//		dlist.printList(dlist);
//
//		System.out.println("Insert at the first position:");
//		dlist.insert(dlist, 1, 13);
//		dlist.printList(dlist);
//
//		System.out.println("Insert at position 4:");
//		dlist.insert(dlist, 4, 5);
//		dlist.printList(dlist);
//
//		System.out.println("Insert at the last position:");
//		dlist.insert(dlist, 10, 7);
//		dlist.printList(dlist);
//
//		System.out.println("Sort the inorder list:");
//		dlist.sort(dlist);
//		dlist.printList(dlist);
//		
//		System.out.println("Query the number and get the query times:");
//		dlist.binarySearch(dlist,7);
//		dlist.printList(dlist);
//	}
}
